package Charm_Seq;

import java.io.IOException;

import java.util.Map.Entry;
import java.util.*;


/**
 * 挖掘长度为2
 * @author Administrator
 *
 */
public class AlgoCharm_Bitset {
        protected Itemsets closedItemsets = new Itemsets();
        protected Context context;
        
	private long startTimestamp; // for stats
	private long endTimestamp; // for stats
	private int minsupRelative;

	//子序列，基因编码
	Map<String, BitSet> mapItemTIDS = new HashMap<String, BitSet>();//最长2公共子序列保存的变量

	int tidcount;
	private int itemsetCount;

	// for optimization with a hashTable
	private HashTable hash;

	public AlgoCharm_Bitset() {
	}

	/**
	 * This algorithm has two parameters
	 * 
	 * @param minsupp
	 *            the minimum support
	 * @param itemCount
	 * @return
	 * @throws IOException
	 */
	public Itemsets runAlgorithm(Context context, double minsup,
			int hashTableSize) {
		this.hash = new HashTable(hashTableSize);
		startTimestamp = System.currentTimeMillis();

		// (1) count the tid set of each item in the database in one database
		// pass
		mapItemTIDS = new HashMap<String, BitSet>(); // id item, count
		tidcount = 0;
		//寻找长度为2的公共子序列
		for(int i=0; i<context.size(); i++) { // for each transaction
//			for(int i=0; i<1; i++) { // for each transaction
			//将排好序的基因序列标号拼接成字符串（203514..）
			String str="";
			for(Integer s:context.getObjects().get(i).getItems()) {
				str+=s+"";
			}
//			System.out.println(str);
			//遍历str字符串，每次将两个相邻的字符拼接成新的字符串，组成map的key map的value就是当前遍历的基因第几条
			//mapItemTIDS map就是存放的长度为2的序列及所在条数的集合，map:["03"，{1,2,3,4},...]
			String str2=str.substring(0,2);
			for (int j=0; j<str.length()-1; j=j+1) {
				str2=str.substring(j,j+2);
				BitSet tids = mapItemTIDS.get(str2);
				if (tids == null) {
					tids = new BitSet();
					mapItemTIDS.put(str2, tids);
				}
				tids.set(tidcount+1);	
			}
			tidcount++;
		}
		
		System.out.print("挖掘长度为2的公共子序列为：");
		for(Entry<String, BitSet> entry: mapItemTIDS.entrySet()) {
			if(entry.getValue().cardinality()>=2)
			System.out.println(entry.getKey()+":"+entry.getValue());
		}
		

//		this.minsupRelative = (int) Math.ceil(minsup * tidcount);
		this.minsupRelative = 2;//指定基因序列最少出现的公共次数。（公共子序列）

		// (2) create ITSearchTree with root node
		//创建基因搜索树 root表示节点
		ITSearchTree tree = new ITSearchTree();
		ITNode root = new ITNode(new HashSet<Integer>());
		//创建根节点，tidset为空，长度为所占基因条数
		root.setTidset(null, tidcount);
		tree.setRoot(root);

		// (3) create childs of the root node.
		//遍历mapItemTIDS，长度为2的基因序列
		for (Entry<String, BitSet> entry : mapItemTIDS.entrySet()) {
			int entryCardinality = entry.getValue().cardinality();
			// we only add nodes for items that are frequents
			//因为mapItemTIDS里面的值并不全是公共序列，有些只在一条出现过，所以进行筛选
			if (entryCardinality >= minsupRelative) {
				// create the new node
				System.out.println(entry.getKey()+":"+entry.getValue());
				//将mapItemTIDS的key（长度为2的公共子序列）转换成itemset的链表set集合中去【13,03,14...】
				Set<Integer> itemset = new HashSet<Integer>();
				itemset.add(Integer.parseInt(entry.getKey()));
				//将长度为2的公共子序列，创建一个新的根节点（基因搜索树的第二层）
				ITNode newNode = new ITNode(itemset);
				//tidset为序列所在基因行集合，cardinality为序列所在基因行总数
				newNode.setTidset(entry.getValue(), entryCardinality);
				newNode.setParent(root);//设置父节点-根节点
				// add the new node as child of the root node
				//添加root根节点的子节点
				root.getChildNodes().add(newNode);
			}
		}//遍历完mapItemTIDS，基因搜索树的第二层结构（长度为2的公共子序列）就出来了了
		
//		for(ITNode it:root.getChildNodes()) {
//			System.out.println(it.getTidset());
//			for(Integer i:it.getItemset()) {
//				System.out.print(i+",");
//			}
//			System.out.println("");
//		}

		// for optimization
		sortChildren(root);

		
		//继续往第二层的结构下拓展
		System.out.println("长度大于2的公共子序列:");
		while (root.getChildNodes().size() > 0) {
			ITNode child = root.getChildNodes().get(0);
			extend(child);
			save(child);
			delete(child);
		}

		saveAllClosedItemsets();
		endTimestamp = System.currentTimeMillis();
        return closedItemsets;
	}
        
        public long getExecTime(){
            return endTimestamp - startTimestamp;
        }

	private void saveAllClosedItemsets() {
		for (List<Itemset> hashE : hash.table) {
			if (hashE != null) {
				for (Itemset itemsetObject : hashE) {
					closedItemsets.addItemset(itemsetObject);
					itemsetCount++;
				}
			}
		}
	}

	private void extend(ITNode currNode) {
		//找到当前节点父节点的子节点的事务集
		Itemset itemset = currNode.getParent().getChildNodes().get(0).itemsetObject;
		//获取当前公共子序列长度
		String itemStr = itemset.getItems().toArray()[0].toString();
		int l=itemStr.length();
		//获取三三组合的前缀列标签
		itemStr.substring(l-1, l);
		String c1=itemStr.substring(l-1, l);
		//循环找出可以可以组合的列标签
		for(Entry<String, BitSet> en:mapItemTIDS.entrySet()) {
			//判断是否是公共子序列
			if(en.getValue().cardinality()>=minsupRelative) {
				String brother = en.getKey();
				//这里主要是补上强转成int类型后缺漏的0(比如05，强转之后会变成5)
				if(brother.length()<2) {
					brother="0"+brother;
				}
				//不需要全部组合，只需要到五五组合就可以
				ITNode candidate=null;
				//如果是可以组合的公共子序列，就创建当前节点的子节点
				if(brother.substring(0,1).equals(c1)) {
					candidate = getCandidate(currNode, brother);
				}
				if (candidate != null) {
					//如果创建子节点成功，就添加到当前节点下
					currNode.getChildNodes().add(candidate);
					candidate.setParent(currNode);
					String str=candidate.itemsetObject.toString();
					if(str.length()==3) {
						str="0"+str;
					}
					System.out.println(str+":"+candidate.itemsetObject.tidset);
				}
			}
		}
		//按照基因集排序
		sortChildren(currNode);
		//继续往下构建(第三层，第四层等)
		while (currNode.getChildNodes().size() > 0) {
			ITNode child = currNode.getChildNodes().get(0);
			extend(child);
			save(child);
			delete(child);
		}
	}

	private ITNode getCandidate(ITNode currNode, String brother) {
		//复制当前节点的基因集
		BitSet commonTids = (BitSet) currNode.getTidset().clone();
		//算出公共子序列交集，减少查询
		commonTids.and(mapItemTIDS.get(brother));
		int cardinality = commonTids.cardinality();
		//如果不是公共子序列，剔除
		if (cardinality >= minsupRelative) {
			//组合序列后面的序列加上
			String brotherEndStr=brother.substring(1,brother.length());
			Set<Integer> union = new HashSet<>();
			union.add(Integer.parseInt((currNode.getItemset().toArray()[0]+brotherEndStr)));
			//只需要五五组合，如果需要满组合，可以注释掉
			if((currNode.getItemset().toArray()[0]+brotherEndStr).length()>=tidcount){
				return null;
			}
			//创建子节点返回出去加到当前节点的子节点下
			ITNode node = new ITNode(union);
			node.setItemset(union);
			node.setTidset(commonTids, cardinality);
			return node;
		}
		return null;
	}

	private void delete(ITNode child) {
		child.getParent().getChildNodes().remove(child);
	}

	private void save(ITNode node) {
		if (!hash.containsSupersetOf(node.itemsetObject)) {
			hash.put(node.itemsetObject);
		}
	}

	private void sortChildren(ITNode node) {
		Collections.sort(node.getChildNodes(), new Comparator<ITNode>() {
			public int compare(ITNode o1, ITNode o2) {
				return o1.getTidset().cardinality() - o2.getTidset().cardinality();
			}
		});
	}

	private void clearNotMapItemTIDS(){
		//将不是公共子序列记录下来
		List<Entry<String,BitSet>> entryList=new ArrayList<>();
		for(Entry<String, BitSet> entry: mapItemTIDS.entrySet()) {
			if(entry.getValue().cardinality()<2){
				entryList.add(entry);
			}
		}
		//从公共子序列中删除
		for(int i=0;i<entryList.size();i++){
			mapItemTIDS.remove(entryList.get(i).getKey(),entryList.get(i).getValue());
		}
	}

	private boolean containsAll(ITNode node1, ITNode node2) {
		BitSet newbitset = (BitSet) node2.getTidset().clone();
		newbitset.and(node1.getTidset());
		return newbitset.cardinality() == node2.size();
	}

	private void replaceInSubtree(ITNode currNode, Set<Integer> itemset) {
		// make the union
		Set<Integer> union = new HashSet<Integer>(itemset);
		union.addAll(currNode.getItemset());
		// replace for this node
		currNode.setItemset(union);
		// replace for the childs of this node
		currNode.replaceInChildren(union);
	}
}